package lc.Q200_250;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 *
 * 整数除法仅保留整数部分。
 * s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
 *
 * 你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
 *
 * 注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
 */
public class Q227 {

    public static void main(String[] args) {
        Q227 q227 = new Q227();
        System.out.println(q227.calculate2(" 282-1*2*13-30-2*2*2/2-95/5*2+55+804+3024"));
    }

    public int calculate2(String s) {
        char preOperator = '+';
        String trimS = s.replace(" ", "");
        Deque<Integer> stack = new LinkedList<>();
        int num = 0;
        for (int i = 0; i < trimS.length(); i++) {
            char c = trimS.charAt(i);
            if (c == '+' || c == '-' || c == '*' || c == '/') {
                // 计算数字
                switch (preOperator) {
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    case '/':
                        stack.push(stack.pop() / num);
                        break;
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                }
                preOperator = c;
                num = 0;
            } else {
                num = num * 10 + (c - '0');
            }
        }
        // 计算一次
        switch (preOperator) {
            case '*':
                stack.push(stack.pop() * num);
                break;
            case '/':
                stack.push(stack.pop() / num);
                break;
            case '+':
                stack.push(num);
                break;
            case '-':
                stack.push(-num);
                break;
        }
        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }

    public int calculate(String s) {
        // 同时使用两个栈
        // 可以优化成只需要一个数字栈，并记录前一个符号即可,见calculate2
        String trimS = s.replace(" ", "");
        Deque<Integer> numberStack = new LinkedList<>();
        Deque<Character> operatorStack = new LinkedList<>();
        int num = 0;
        for (int i = 0; i < trimS.length(); i++) {
            char c = trimS.charAt(i);
            if (c == '+' || c == '-' || c == '*' || c == '/') {
                // 数字入栈
                numberStack.push(num);
                if (operatorStack.isEmpty()) {
                    operatorStack.push(c);
                } else {
                    if (c == '+' || c == '-') {
                        // 计算
                        // 前面的全部计算出来
                        while (!operatorStack.isEmpty()) {
                            Character c1 = operatorStack.pop();
                            Integer n1 = numberStack.pop();
                            Integer n2 = numberStack.pop();
                            switch (c1) {
                                case '+':
                                    numberStack.push(n1 + n2);
                                    break;
                                case '-':
                                    numberStack.push(n2 - n1);
                                    break;
                                case '*':
                                    numberStack.push(n1 * n2);
                                    break;
                                case '/':
                                    numberStack.push(n2 / n1);
                                    break;
                            }
                        }

                        operatorStack.push(c);
                    } else {
                        Character peek = operatorStack.peek();
                        if (peek == '+' || peek == '-') {
                            // 符号入栈
                            operatorStack.push(c);
                        } else {
                            // 不需要将前面都算出来？
                            operatorStack.pop();
                            Integer n1 = numberStack.pop();
                            Integer n2 = numberStack.pop();
                            switch (peek) {
                                case '*':
                                    numberStack.push(n1 * n2);
                                    break;
                                case '/':
                                    numberStack.push(n2 / n1);
                                    break;
                            }
                            operatorStack.push(c);
                        }
                    }
                }
                num = 0;
            } else {
                num = num * 10 + (c - '0');
            }
        }
        numberStack.push(num);
        // 先判断最后一个
        if (!operatorStack.isEmpty()) {
            // 计算
            Character c1 = operatorStack.pop();
            Integer n1 = numberStack.pop();
            Integer n2 = numberStack.pop();
            switch (c1) {
                case '+':
                    numberStack.push(n1 + n2);
                    break;
                case '-':
                    numberStack.push(n2 - n1);
                    break;
                case '*':
                    numberStack.push(n1 * n2);
                    break;
                case '/':
                    numberStack.push(n2 / n1);
                    break;
            }
        }
        // 剩下的从左向右处理
        while (!operatorStack.isEmpty()) {
            Character poll = operatorStack.pollLast();
            int n1 = numberStack.pollLast();
            int n2 = numberStack.pollLast();
            switch (poll) {
                case '+':
                    numberStack.offer(n1 + n2);
                    break;
                case '-':
                    numberStack.offer(n1 - n2);
                    break;
                case '*':
                    numberStack.offer(n1 * n2);
                    break;
                case '/':
                    numberStack.offer(n1 / n2);
                    break;
            }
        }
        if (numberStack.isEmpty()) {
            return 0;
        }
        return numberStack.pop();
    }
}
